package 我的Java学习_算法基础.day_02;

public class _017_二分查找 {
    public static void main(String[] args) {
        int[] a={1,4,7,9,11};
        int s = binarySearch(a,0,4,8);
        System.out.println(s);
    }

    /**
     *
     * @param arr       由小到大排列的数组
     * @param low       找寻范围的第一个元素下标
     * @param high      找寻范围的最后一个元素下标
     * @param key       找寻的数值
     * @return          数组中值等于key的下标
     */
    private static int binarySearch(int[] arr,int low,int high,int key){
        if(low>high){
            return -1;
        }
        int mid=low+((high-low)>>1);    //(low+high)>>>1;//防止溢出，移位也更高效
        int midVal=arr[mid];
        if(midVal<key){
            return binarySearch(arr,mid+1,high,key);
        }else if(midVal>key){
            return binarySearch(arr,low,mid-1,key);
        }else {
            return mid;//key found
        }
    }
}
